#include "graph_and_tree.h"
#include "kaldi-common.h"


#include <fstream>
#include <iostream>
#include <boost/xpressive/xpressive.hpp>
#include <boost/algorithm/string.hpp>


namespace GRAPHTREE{

	////////////////////////       normal functions ///////////////////////////
	int SplitString(const std::string& s, std::vector<std::string>& s_parts)
	{
		using namespace boost::xpressive;
		KALDI_ASSERT(&s_parts != nullptr);
		boost::split(s_parts, s, boost::is_any_of(" "), boost::token_compress_off);
		return s_parts.size() > 0 ? s_parts.size():-1;
	}


	//////////////////////////////////////////////////////////////////////////
	Arc* State::AddArc(Arc* new_arc){
		if (new_arc)
		{
			arcs_.push_back(new_arc);
			SortArcs();
		}
		return new_arc;
	}

	void State::SortArcs(){
			for (int i=1;i<arcs_.size();i++)
			{
				Arc* key = arcs_[i];
				int j=i-1;
				while(j>=0 && arcs_[j]->Weight() > key->Weight()){
					Arc* tmp = key;
					key = arcs_[j];
					arcs_[j] = tmp;
					j--;
				}
				arcs_[j+1] = key;
			}

	}

	//////////////////////////////////////////////////////////////////////////
	template <typename Elem> Int64 FstGraph<Elem>::elementAlloc_ = 2048;
	template <typename Elem>
	FstGraph<Elem>::FstGraph(const char* fst_file_name):WFSTGraph()
	{
		ResizeStates(elementAlloc_);
		ResizeArcs(elementAlloc_);
		Read(fst_file_name, false);

	}

	template <typename Elem>
	FstGraph<Elem>::~FstGraph()
	{
		FreeList<State>(states_list_);
		FreeList<Arc>(arcs_list_);
		FreeList<Token>(token_list_);

	}

	template <typename Elem>
	void FstGraph<Elem>::FindSccs(State* graph_root, std::vector<State*>& sccs){

	}

	template <typename Elem>
	void FstGraph<Elem>::AddArc2State(StateId state_id, Arc* new_arc)
	{
		mStates[state_id]->AddArc(new_arc);
	}

	template <typename Elem>
	void FstGraph<Elem>::Read(const std::string& fst_file_name, bool is_binary /* = true */)
	{
		using namespace std;
		using namespace kaldi;
		typedef long long stateId;
		if (is_binary)
		{
		}else{
			
			KALDI_ASSERT(! file_name.empty());
			stateId s = 0;
			std::ifstream istrm(fst_file_name.c_str(), ios_base::in);
			if (istrm.good()){
				std::string fst_line;
				std::vector<std::string> lineUnits;
				int link_index = 0;
				while (istrm.eof() == false)
				{
					std::getline(istrm, fst_line, '\n');
					if (! fst_line.empty())
					{
						if (SplitString(fst_line, lineUnits) >= 2)
						{
							int start, end;
							std::string i_label, o_label;
							float trans_weight;
							if (lineUnits.size()>4)
							{
								start = std::atoi(lineUnits[0].c_str());
								end = std::atoi(lineUnits[1].c_str());
								i_label = lineUnits[2];
								o_label = lineUnits[3];
								trans_weight = std::atof(lineUnits[4].c_str());

								State* new_state1 = NewState(start);
								state* new_state2 = NewState(end);
								Arc* new_arc = NewArc(link_index++);
								new_arc->SetArcStartId(start);
								new_arc->SetArcEndId(end);
								new_arc->SetIlabel(i_label);
								new_arc->SetOlabel(o_label);
								new_arc->SetWeight(trans_weight);
								AddArc2State(new_state1->StateId(), new_arc);
								
								

							}else{
								end = std::atoi(lineUnits[0].c_str());
								trans_weight = std::atof(lineUnits[1].c_str());
								State* new_state1 = NewState(end);
								new_state1->SetWeight(trans_weight);
							}
						}


					}
				}

				istrm.close();
			}

		}
	}


	template <typename Elem>
	float FstGraph<Elem>::SingleSourceShortestPath(State* src, State** dst_state){
		KALDI_ASSERT(dst_state = !nullptr);
		KALDI_ASSERT(src ! = nullptr);
		float path_weight = 0.0f;


		return path_weight;

	}


	//////////////////////////////////////////////////////////////////////////

	int NormalTree::sLinkAllc = 1024;
	int NormalTree::sNodeAllc = 1024;

	NormalTree::~NormalTree()
	{
		//free links
		TreeLink* this_link = mLinkHead;
		TreeLink* next_link = nullptr;
		while(this_link){
			next_link = this_link->tail;
			delete this_link;
			this_link = next_link;
			
		}

		//free nodes
		TreeNode* this_node = mNodeHead, *next_node = nullptr;
		while(this_node){
			next_node = this_node->tail;
			delete this_node;
			this_node = next_node;
		}

		// and so on
	}

	void NormalTree::ConstructTree(const std::string& file_name){
		using namespace std;
		using namespace kaldi;
		typedef long long stateId;
		KALDI_ASSERT(! file_name.empty());
		stateId s = 0;
		SetNodesSize(sNodeAllc);
		SetLinksSize(sLinkAllc);
		std::ifstream istrm(file_name.c_str(), ios_base::in);
		if (istrm.good()){
			std::string fst_line;
			std::vector<std::string> lineUnits;
			int link_index = 0;
			while (istrm.eof() == false)
			{
				std::getline(istrm, fst_line, '\n');
				if (! fst_line.empty())
				{
					if (SplitString(fst_line, lineUnits) >= 2)
					{
						int start, end;
						std::string i_label, o_label;
						float trans_weight;
						if (lineUnits.size()>4)
						{
							start = std::atoi(lineUnits[0].c_str());
							end = std::atoi(lineUnits[1].c_str());
							i_label = lineUnits[2];
							o_label = lineUnits[3];
							trans_weight = std::atof(lineUnits[4].c_str());

							TreeNode* new_node1 = GetNode(start);
							TreeNode* new_node2 = GetNode(end);
							
							TreeLink* new_link = GetLink(link_index++);
							AddLink2Node(new_node1, new_link);
							new_link->SetPrevNode(new_node1);
							new_link->SetNextNode(new_node2);
							if (mTreeRoot == nullptr)
							{
								mTreeRoot = new_node1;
							}

						}else{
							end = std::atoi(lineUnits[0].c_str());
							trans_weight = std::atof(lineUnits[1].c_str());
							TreeNode* new_node1 = GetNode(end);
							TreeLink* new_link = GetLink(link_index++);
							new_link->SetNextNode(new_node1);

						}
					}
					

				}
			}

			istrm.close();
		}
	}

	int NormalTreeRun(int argc, char* argv[]){
		NormalTree tree;
		tree.ConstructTree(argv[0]);

		return 0;
	}

}